﻿using System.Diagnostics;

namespace Graph;

//树是图的无环联通子图；
//QuickUnion
public class UnionFindForest : IUF
{
    private int[] parent; //记录并查森林中每个顶点所属并查树中父级顶点编号。

    public UnionFindForest(int size) //size：顶点数量
    {
        parent = new int[size];

        for (int i = 0; i < size; i++)
        {
            parent[i] = i; //每个顶点独自成为一颗并查树且为根节点。
        }
    }

    public int Size => parent.Length;

    //查找顶点p所在并查树的根节点编号 O（h）
    private int Find(int p)
    {
        while (p != parent[p]) //if p==parent[p], then p is root;
        {
            p = parent[p];
        }

        return p;
    }

    //查看顶点p，q是否联通（属于同一颗树） O（h）
    public bool IsConnected(int p, int q)
    {
        return Find(p) == Find(q); //根节点相同，就在同一颗树
    }

    //合并p，q 所在集合（合并为同一颗树） O（h）
    public void Union(int p, int q)
    {
        int pRoot = Find(p);
        int qRoot = Find(q);

        if (pRoot == qRoot)
        {
            return;
        }

        parent[pRoot] = qRoot; //仅对根节点操作，合并性能高，降低树的高度，压缩了查询路径。
    }

    //并查集时间测试
    private static long TestUF(IUF uF, int m)
    {
        int size = uF.Size;
        Random rnd = new Random();
        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();

        for (int i = 0; i < m; i++)
        {
            int a = rnd.Next(size);
            int b = rnd.Next(size);
            uF.Union(a, b);
        }

        for (int i = 0; i < m; i++)
        {
            int a = rnd.Next(size);
            int b = rnd.Next(size);
            uF.IsConnected(a, b);
        }

        stopwatch.Stop();
        return stopwatch.ElapsedMilliseconds;
    }

    //验证
    static void Main(string[] args)
    {
        //int size = 10000;
        int size = 100000;
        
        int m = 10000;

        UnionFindSet ufs = new UnionFindSet(size);
        Console.WriteLine("UnionFindSet: " + TestUF(ufs, m) + " ms");

        UnionFindForest uft = new UnionFindForest(size);
        Console.WriteLine("UnionFindTree: " + TestUF(uft, m) + " ms");

        Console.Read();
    }
}
